package org.example;

import apple.laf.JRSUIUtils;
import sun.lwawt.macosx.CImage;

import java.util.*;

public class AppTest06 {
    // 566 重塑矩阵
    class Solution {
        // 3
        public int[][] matrixReshape(int[][] mat, int r, int c) {
            int m = mat.length, n = mat[0].length;
            if (m * n != r * c) return mat;
            int[][] ans = new int[r][c];
            for (int i = 0; i < m * n; i++) {
                ans[i / c][i % c] = mat[i / m][i % n];
            }
            return ans;
        }
    }

    // 575 Distribute Candies
    class Solution {
        // 2
        public int distributeCandies(int[] candies) {
            HashSet<Integer> kinds = new HashSet<>();
            for (int candy : candies) {
                kinds.add(candy);
            }
            return Math.min(kinds.size(), candies.length / 2);
        }
        // 2
        public int distributeCandies(int[] candies) {
            HashSet<Integer> kinds = new HashSet<>();
            for (int candy : candies) {
                kinds.add(candy);
            }
            return Math.min(kinds.size(), candies.length / 2);
        }
    }

    // 594 Longest Harmonous Sequence
    public class Solution {
        // 1
        public int findLHS(int[] nums) {
            HashMap<Integer, Integer> map = new HashMap<>();
            int res = 0;
            for (int num : nums) {
                map.put(num, map.getOrDefault(num, 0) + 1);
            }
            for (int key : map.keySet()) {
                if (map.containsKey(key + 1)) {
                    res = Math.max(res, map.get(key) + map.get(key + 1));
                }
            }
            return res;
        }
        // 2
        public int findLHS(int[] nums) {
            HashMap<Integer, Integer> map = new HashMap<>();
            for (int num : nums) {
                map.put(num, map.getOrDefault(num, 0) + 1);
            }
            int ans = 0;
            for (int key : map.keySet()) {
                if (map.containsKey(key + 1)) {
                    ans = Math.max(ans, map.get(key) + map.get(key + 1));
                }
            }
            return ans;
        }
        // 3
        public int findLHS(int[] nums) {
            HashMap<Integer, Integer> map1 = new HashMap<>();
            for (int num : nums) {
                map1.put(num, map1.getOrDefault(num, 0) + 1);
            }
            int ans = 0;
            for (int key : map1.keySet()) {
                if (map1.containsKey(key + 1)) {
                    ans = Math.max(ans, map1.get(key) + map1.get(key + 1));
                }
            }
            return ans;
        }
    }

    // 598 Range Sum II
    public class Solution {
        // 1
        public int maxCount(int m, int n, int[][] ops) {
            for (int[] op : ops) {
                m = Math.min(m, op[0]);
                n = Math.min(n, op[1]);
            }
            return m * n;
        }
        // 2
        public int maxCount(int m, int n, int[][] ops) {
            for (int[] op : ops) {
                m = Math.min(m, op[0]);
                n = Math.min(n, op[1]);
            }
            return m * n;
        }
        // 3
        public int maxCount(int m, int n, int[][] ops) {
            for (int[] : ops) {
                m = Math.min(m, ops[0]);
                n = Math.min(n, ops[1]);
            }
            return m * n;
        }
    }

    // 599 最小索引总和
    class Solution {
        // 1
        public String[] findRestaurant(String[] list1, String[] list2) {
            HashMap<String, Integer> map = new HashMap<>();
            for (int i = 0; i < list1.length; i++) {
                map.put(list1[i], i);
            }

            List<String> res = new ArrayList<>();
            int min_sum = Integer.MAX_VALUE, sum;
            for (int j = 0; j < list2.length && j <= min_sum; j++) {
                if (map.containsKey(list2[j])) {
                    sum = j + map.get(list2[j]);
                    if (sum < min_sum) {
                        res.clear();
                        res.add(list2[j]);
                        min_sum = sum;
                    } else if (sum == min_sum){
                        res.add(list2[j]);
                    }
                }
            }
            return res.toArray(new String[res.size()]);
        }
        // 2
        public String[] findRestaurant(String[] list1, String[] list2) {
            HashMap<String, Integer> map1 = new HashMap<>();
            for (int i = 0; i < list1.length; i++) {
                map1.put(list1[i], i);
            }
            int min_sum = Integer.MAX_VALUE, sum;
            List<String> res = new ArrayList<>();
            for (int j = 0; j < list2.length && j <= min_sum; j++) {
                if (map1.containsKey(list2[j])) {
                    sum = map1.get(list2[j]) + j;
                    if (sum < min_sum) {
                        res.clear();
                        res.add(list2[j]);
                        min_sum = sum;
                    } else if (sum == min_sum) {
                        res.add(list2[j]);
                    }
                }
            }
            return res.toArray(new String[res.size()]);
        }
        // 3
        public String[] findRestaurant(String[] list1, String[] list2) {
            HashMap<String, Integer> map1 = new HashMap<>();
            for (int i = 0; i < list1.length; i++) {
                map1.put(list1[i], i);
            }
            List<String> ans = new ArrayList<>();
            int min_sum = Integer.MAX_VALUE, sum;
            for (int j = 0; j < list2.length && j <= min_sum; j++) {
                if (map1.containsKey(list2[j])) {
                    sum = j + map1.get(list2[j]);
                    if (sum < min_sum) {
                        ans.clear();
                        ans.add(list2[j]);
                        min_sum = sum;
                    } else if (sum == min_sum){
                        ans.add(list2[j]);
                    }
                }
            }
            return ans.toArray(new String[ans.size()]);
        }
    }

    // 605 种花问题
    class Solution {
        // 1
        public boolean canPlaceFlowers(int[] flowerbed, int n) {
            int count = 0;
            for (int i = 0; i < flowerbed.length; i++) {
                if (flowerbed[i] == 0 && (i == 0 || flowerbed[i - 1] == 0) && (i == flowerbed.length - 1 || flowerbed[i + 1] == 0)) {
                    flowerbed[i++] = 1;
                    count++;
                }
                if (count >= n) return true;
            }
            return false;
        }
        // 2
        public boolean canPlaceFlowers(int[] flowerbed, int n) {
            int count = 0;
            for (int i = 0; i < flowerbed.length; i++) {
                if (flowerbed[i] == 0 && (i == 0 || flowerbed[i - 1] == 0) && (i == flowerbed.length - 1 || flowerbed[i + 1] == 0)) {
                    // todo 花槽置为1
                    flowerbed[i++] = 1;
                    count++;
                }
                if (count >= n) return true;
            }
            return false;
        }
        // 3
        public boolean canPlaceFlowers(int[] flowerbed, int n) {
            int count = 0;
            for (int i = 0; i < flowerbed.length; i++) {
                if (flowerbed[i] == 0 && (i == 0 || flowerbed[i - 1] == 0) && (i == flowerbed.length - 1 || flowerbed[i + 1] == 0)) {
                    flowerbed[i++] = 1;
                    count++;
                }
                if (count >= n) return true;
            }
            return false;
        }
    }

    // 606 根据二叉树创建字符串
    class Solution {
        // 1
        public String tree2str(TreeNode root) {
            if (root == null) return "";
            if (root.left == null && root.right == null) return root.val + "";
            if (root.right == null) {
                return root.val + "(" + tree2str(root.left) + ")";
            }
            return root.val + "(" + tree2str(root.left) + ")(" + tree2str(root.right) + ")";
        }
        // 2
        public String tree2str(TreeNode root) {
            if (root == null) return "";
            if (root.left == null && root.right == null) return root.val + "";
            if (root.right == null) return root.val + "(" +tree2str(root.left) + ")";
            return root.val + "(" + tree2str(root.left) + ")(" + tree2str(root.right) + ")";
        }
        // 3
        public String tree2str(TreeNode root) {
            if (root == null) return "";
            if (root.left == null && root.right == null) return root.val + "";
            if (root.right == null) return root.val + "(" + tree2str(root.left) + ")";
            return root.val + "(" + tree2str(root.left) + ")(" + tree2str(root.right) + ")";
        }
    }

    // 617 合并二叉树
    class Solution {
        // 1
        public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
            if (t1 == null) return t2;
            if (t2 == null) return t1;
            t1.val += t2.val;
            t1.left = mergeTrees(t1.left, t2.left);
            t1.right = mergeTrees(t1.right, t2.right);
            return t1;
        }
        // 2
        public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
            if (t1 == null) return t2;
            if (t2 == null) return t1;
            t1.val += t2.val;
            t1.left = mergeTrees(t1.left, t2.left);
            t1.right = mergeTrees(t1.right, t2.right);
            return t1;
        }
        // 3
        public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
            if (t1 == null) return t2;
            if (t2 == null) return t1;
            t1.val += t2.val;
            t1.left = mergeTrees(t1.left, t2.left);
            t1.right = mergeTrees(t1.right, t2.right);
            return t1;
        }
    }

    // 628 三个数最大乘积
    class Solution {
        // 2
        public int maximumProduct(int[] nums) {
            int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
            int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE,max3 = Integer.MIN_VALUE;
            for (int num : nums) {
                if (num < min1) {
                    min2 = min1;
                    min1 = num;
                }
                else if (num < min2) min2 = num;
                if (num > max1) {
                    max3 = max2;
                    max2 = max1;
                    max1 = num;
                } else if (num > max2) {
                    max3 = max2;
                    max2 = num;
                } else if (num > max3) max3 = num;
            }
            return Math.max(min1 * min2 * max1, max1 * max2 * max3);
        }
        // 3
        public int maximumProduct(int[] nums) {
            int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;
            int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
            for (int num : nums) {
                if (num > max1) {
                    max3 = max2;
                    max2 = max1;
                    max1 = num;
                } else if (num > max2) {
                    max3 = max2;
                    max2 = num;
                } else if (num > max3) max3 = num;
                if (num < min1) {
                    min2 =min1;
                    min1 = num;
                } else if (num < min2) min2 = num;
            }
            return Math.max(max1 * max2 * max3, max1 * min1 * min2);
        }
    }

    // 637 二叉树层平均值
    class Solution {
        // 1
        public List<Double> averageOfLevels(TreeNode root) {
            List<Double> averages = new ArrayList<>();
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                double sum = 0;
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    TreeNode node = queue.poll();
                    sum += node.val;
                    TreeNode left = node.left, right = node.right;
                    if (left != null) queue.offer(left);
                    if (right != null) queue.offer(right);
                }
                averages.add(sum / size);
            }
            return averages;
        }
        // 2
        public List<Double> averageOfLevels(TreeNode root) {
            List<Double> res = new ArrayList<>();
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                double sum = 0;
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    TreeNode node = queue.poll();
                    if (node.left != null) queue.offer(node.left);
                    if (node.right != null) queue.offer(node.right);
                    sum += node.val;
                }
                Double average = sum * 1.0 / size;
                res.add(average);
            }
            return res;
        }
        // 3
        public List<Double> averageOfLevels(TreeNode root) {
            List<Double> ans = new ArrayList<>();
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                int size = queue.size();
                // todo 注意要用 double
                double sum = 0;
                for (int i = 0; i < size; i++) {
                    TreeNode node = queue.poll();
                    sum += node.val;
                    if (node.left != null) queue.add(node.left);
                    if (node.right != null) queue.add(node.right);
                }
                Double average = sum * 1.0 / size;
                ans.add(average);
            }
            return ans;
        }
    }

    // 643 子数组的最大平均数
    class Solution {
        // 1
        public double findMaxAverage(int[] nums, int k) {
            int sum = 0;
            for (int i = 0; i < k; i++) {
                sum += nums[i];
            }
            int maxSum = sum;
            for (int i = k; i < nums.length; i++) {
                sum = sum + nums[i] - nums[i - k];
                maxSum = Math.max(maxSum, sum);
            }
            return maxSum * 1.0 / k;
        }
        // 2
        public double findMaxAverage(int[] nums, int k) {
            int sum = 0;
            for (int i = 0; i < k; i++) {
                sum += nums[i];
            }
            int maxSum = sum;
            for (int i = k; i < nums.length; i++) {
                sum = sum + nums[i] - nums[i - k];
                maxSum = Math.max(maxSum, sum);
            }
            return maxSum * 1.0 / k;
        }
        // 3
        public double findMaxAverage(int[] nums, int k) {
            int sum = 0;
            for (int i = 0; i < k; i++) {
                sum += nums[i];
            }
            int maxSum = sum;
            for (int i = k; i < nums.length; i++) {
                sum = sum + nums[i] - nums[i - k];
                maxSum = Math.max(maxSum, sum);
            }
            return maxSum * 1.0 / k;
        }
    }

    // 645 错误的集合
    class Solution {
        // 1
        public int[] findErrorNums(int[] nums) {
            Map<Integer, Integer> map = new HashMap<>();
            int dup = -1, missing = 1;
            for (int num : nums){
                map.put(num, map.getOrDefault(num, 0) + 1);
            }
            for (int i = 1; i <= nums.length; i++) {
                if (map.containsKey(i)) {
                    if (map.get(i) == 2 ) dup = i;
                } else missing = i;
            }
            return new int[]{dup, missing};
        }
        // 2
        public int[] findErrorNums(int[] nums) {
            HashMap<Integer, Integer> frequencyMap = new HashMap<>();
            int dup = 0, missing = 0;
            for (int num : nums) {
                frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
            }
            for (int i = 1; i <= nums.length; i++){
                if (frequencyMap.containsKey(i)) {
                    if (frequencyMap.get(i) == 2) {
                        dup = i;
                    }
                } else {
                    missing = i;
                }
            }
            return new int[]{dup, missing};
        }
        // 3
        public int[] findErrorNums(int[] nums) {
            HashMap<Integer, Integer> map = new HashMap<>();
            int dup = 0, missing = 0;
            for (int num : nums) {
                map.put(num, map.getOrDefault(num, 0) + 1);
            }
            for (int i = 1; i <= nums.length; i++) {
                if (map.containsKey(i)) {
                    if (map.get(i) == 2) dup = i;
                } else {
                    missing = i;
                }
            }
            return new int[]{dup, missing};
        }
    }

    // 653 两数之和 IV - 输入 BST
    // 1
    public class Solution {
        public boolean findTarget(TreeNode root, int k) {
            Set<Integer> set = new HashSet<>();
            return find(root, k, set);
        }

        public boolean find(TreeNode root, int k, Set<Integer> set) {
            if (root == null) return false;
            if (set.contains(k - root.val)) return true;
            set.add(root.val);
            return find(root.left, k, set) || find(root.right, k, set);
        }
    }
    // 2
    public class Solution {
        public boolean findTarget(TreeNode root, int k) {
            HashSet<Integer> set = new HashSet<>();
            return find(root, k, set);
        }
        public boolean find(TreeNode root, int k, Set<Integer> set) {
            if (root == null) return false;
            if (set.contains(k - root.val)) return true;
            set.add(root.val);
            return find(root.left, k, set) || find(root.right, k, set);
        }
    }
    // 3
    public class Solution {
        public boolean findTarget(TreeNode root, int k) {
            HashSet<Integer> set = new HashSet<>();
            return find(root, k, set);
        }
        public boolean find(TreeNode root, int k, HashSet<Integer> set) {
            if (root == null) return false;
            if (set.contains(k - root.val)) return true;
            set.add(root.val);
            return find(root.left, k, set) || find(root.right, k, set);
        }
    }

    // 657 Robot returns to start point
    class Solution {
        // 1
        public boolean judgeCircle(String moves) {
            int x = 0, y = 0;
            int length = moves.length();
            for (int i = 0; i < length; i++) {
                char move = moves.charAt(i);
                if (move == 'U') y--;
                else if (move == 'D') y++;
                else if (move == 'L') x--;
                else if (move == 'R') x++;
            }
            return x == 0 && y == 0;
        }
        // 2
        public boolean judgeCircle(String moves) {
            int x = 0, y = 0;
            char[] charMoves = moves.toCharArray();
            for (char charMove : charMoves) {
                if (charMove == 'U') y--;
                else if (charMove == 'D') y++;
                else if (charMove == 'L') x--;
                else x++;
            }
            return x == 0 && y == 0;
        }
        // 3
        public boolean judgeCircle(String moves) {
            int x = 0, y = 0;
            char[] moveChars= moves.toCharArray();
            for (char moveChar : moveChars) {
                if (moveChar == 'U') y--;
                else if (moveChar == 'D') y++;
                else if (moveChar == 'L') x--;
                else x++;
            }
            return x == 0 && y == 0;
        }
    }

    // 671 Second Minimum in Binary Tree
    // 1
    class Solution {
        int min;
        long secondMin = Long.MAX_VALUE;

        public void findSecondMin(TreeNode root) {
            if (root != null) {
                if (root.val > min && root.val < secondMin) {
                    secondMin = root.val;
                } else if (root.val == min) {
                    findSecondMin(root.left);
                    findSecondMin(root.right);
                }
            }
        }

        public int findSecondMinimumValue(TreeNode root) {
            min = root.val;
            findSecondMin(root);
            return secondMin < Long.MAX_VALUE ? (int) secondMin : -1;
        }
    }
    // 2
    class Solution {
        int min;
        long secMin = Long.MAX_VALUE;

        public void getSecondMin(TreeNode root) {
            if (root != null) {
                if (root.val > min && root.val < secMin){
                    secMin = root.val;
                } else if (root.val == min) {
                    getSecondMin(root.left);
                    getSecondMin(root.right);
                }
            }
        }

        public int findSecondMinimumValue(TreeNode root) {
            min = root.val;
            getSecondMin(root);
            return secMin == Integer.MAX_VALUE ? -1 : (int) secMin;
        }
    }
    // 3
    class Solution {
        int min;
        long secMin = Long.MAX_VALUE;

        public void depthFirstSearch(TreeNode root) {
            if (root != null) {
                if (root.val > min && root.val < secMin) {
                    secMin = root.val;
                } else if (root.val == min) {
                    depthFirstSearch(root.left);
                    depthFirstSearch(root.right);
                }
            }
        }

        public int findSecondMinimumValue(TreeNode root) {
            min = root.val;
            depthFirstSearch(root);
            return secMin < Long.MAX_VALUE ? (int) secMin : -1;
        }
    }

    // 674 最长连续递增序列
    class Solution {
        // 1
        public int findLengthOfLCIS(int[] nums) {
            int ans = 0, start = 0;
            for (int i = 0; i < nums.length; i++) {
                if (i > 0 && nums[i] <= nums[i - 1]) {
                    start = i;
                }
                ans = Math.max(ans, i - start + 1);
            }
            return ans;
        }
        // 2
        public int findLengthOfLCIS(int[] nums) {
            int anchor = 0, res = 0;
            for (int i = 0; i < nums.length; i++) {
                if (i > 0 && nums[i] <= nums[i - 1]) {
                    anchor = i;
                }
                res = Math.max(res, i - anchor + 1);
            }
            return res;
        }
        // 3
        public int findLengthOfLCIS(int[] nums) {
            int anchor = 0, ans = 0;
            for (int i = 0; i < nums.length; i++) {
                if (i > 0 && nums[i - 1] >= nums[i]) {
                    anchor = i;
                }
                ans = Math.max(ans, i - anchor + 1);
            }
            return ans;
        }
    }

    // 682 Baseball Game
    class Solution {
        // 1
        public int calPoints(String[] ops) {
            Stack<Integer> stack = new Stack<>();
            for (String op : ops) {
                if (op.equals("+")) {
                    int top = stack.pop();
                    int newtop = top + stack.peek();
                    stack.push(top);
                    stack.push(newtop);
                } else if (op.equals("C")) {
                    stack.pop();
                } else if (op.equals("D")) {
                    stack.push(2 * stack.peek());
                } else {
                    stack.push(Integer.valueOf(op));
                }
            }
            int ans = 0;
            for (int score : stack) ans += score;
            return ans;
        }
        // 2
        public int calPoints(String[] ops) {
            Stack<Integer> opsStack = new Stack<>();
            for (String op : ops) {
                if (op.equals("+")) {
                    int last = opsStack.pop();
                    int secLast = opsStack.peek();
                    int sum = last + secLast;
                    opsStack.push(last);
                    opsStack.push(sum);
                } else if (op.equals("C")) {
                    // 删除
                    opsStack.pop();
                } else if (op.equals("D")) {
                    // 翻倍
                    opsStack.push(2 * opsStack.peek());
                } else {
                    opsStack.push(Integer.valueOf(op));
                }
            }
            int ans = 0;
            for (int num : opsStack) {
                ans += num;
            }
            return ans;
        }
        // 3
        public int calPoints(String[] ops) {
            LinkedList<Integer> stack = new LinkedList<>();
            for (String op : ops) {
                if (op.equals("+")) {
                    int first = stack.pop();
                    int second = stack.peek();
                    int newValue = first + second;
                    stack.push(first);
                    stack.push(newValue);
                } else if (op.equals("D")) {
                    stack.push(2 * stack.peek());
                } else if (op.equals("C")) {
                    stack.pop();
                } else {
                    stack.push(Integer.valueOf(op));
                }
            }
            int ans = 0;
            for (int num : stack) {
                ans += num;
            }
            return ans;
        }
    }

    // 690 Importance of Employee
    // 1
    class Solution {
        Map<Integer, Employee> map = new HashMap<Integer, Employee>();

        public int getImportance(List<Employee> employees, int id) {
            for (Employee employee : employees) {
                map.put(employee.id, employee);
            }
            return dfs(id);
        }

        public int dfs(int id) {
            Employee employee = map.get(id);
            int total = employee.importance;
            List<Integer> subordinates = employee.subordinates;
            for (int subId : subordinates) {
                total += dfs(subId);
            }
            return total;
        }
    }
    // 2
    class Solution {
        HashMap<Integer, Employee> map = new HashMap<>();

        public int getImportance(List<Employee> employees, int id) {
            for (Employee employee : employees) {
                map.put(employee.id, employee);
            }
            return depthFirstSearch(id);
        }

        public int depthFirstSearch(int id) {
            Employee root = map.get(id);
            int ans = root.importance;
            for (int subordinate : root.subordinates) {
                ans += depthFirstSearch(subordinate);
            }
            return ans;
        }
    }
    // 3
    class Solution {
        HashMap<Integer, Employee> employeeMap = new HashMap<>();

        public int getImportance(List<Employee> employees, int id) {
            for (Employee employee : employees) {
                employeeMap.put(employee.id, employee);
            }
            return depthsFirstSearch(id);
        }

        public int depthsFirstSearch(int id) {
            Employee root = employeeMap.get(id);
            List<Integer> subs = root.subordinates;
            int totalImportance = root.importance;
            for (Integer sub : subs) {
                totalImportance += depthsFirstSearch(sub);
            }
            return totalImportance;
        }
    }

    // 693 交替位二进制数
    class Solution {
        // 1
        public boolean hasAlternatingBits(int n) {
            String bits = Integer.toBinaryString(n);
            for (int i = 0; i < bits.length() - 1; i++) {
                if (bits.charAt(i) == bits.charAt(i + 1)) {
                    return false;
                }
            }
            return true;
        }
        // 2
        public boolean hasAlternatingBits(int n) {
            String nBinaryString = Integer.toBinaryString(n);
            for (int i = 0; i < nBinaryString.length() - 1; i++) {
                if (nBinaryString.charAt(i) == nBinaryString.charAt(i + 1)) {
                    return false;
                }
            }
            return true;
        }
        // 3
        public boolean hasAlternatingBits(int n) {
            String nBinaryString = Integer.toBinaryString(n);
            for (int i = 0; i < nBinaryString.length() - 1; i++) {
                if (nBinaryString.charAt(i) == nBinaryString.charAt(i + 1)) {
                    return false;
                }
            }
            return true;
        }
    }

    // 696 计算二进制子串
    class Solution {
        // 1
        public int countBinarySubstrings(String s) {
            int ptr = 0, n = s.length(), last = 0, ans = 0;
            while (ptr < n) {
                char c = s.charAt(ptr);
                int count = 0;
                while (ptr < n && s.charAt(ptr) == c) {
                    ++ptr;
                    ++count;
                }
                ans += Math.min(count, last);
                last = count;
            }
            return ans;
        }
        // 2
        public int countBinarySubstrings(String s) {
            int ptr = 0, preCount = 0, ans = 0;
            while (ptr < s.length()) {
                char c = s.charAt(ptr);
                int curCount = 0;
                while (ptr < s.length() && s.charAt(ptr) == c) {
                    curCount++;
                    ptr++;
                }
                ans += Math.min(preCount, curCount);
                preCount = curCount;
            }
            return ans;
        }
        // 3
        public int countBinarySubstrings(String s) {
            int ptr = 0, ans = 0, preCount = 0;
            while (ptr < s.length()) {
                int curCount = 0;
                char c = s.charAt(ptr);
                while (ptr < s.length() && c == s.charAt(ptr)) {
                    curCount++;
                    ptr++;
                }
                ans += Math.min(preCount, curCount);
                preCount = curCount;
            }
            return ans;
        }
    }

    // 697 Degree of Array
    class Solution {
        // 1
        public int findShortestSubArray(int[] nums) {
            Map<Integer, int[]> map = new HashMap<>();
            int n = nums.length;
            for (int i = 0; i < n; i++) {
                if (map.containsKey(nums[i])) {
                    map.get(nums[i])[0]++;
                    map.get(nums[i])[2] = i;
                } else {
                    map.put(nums[i], new int[]{1, i, i});
                }
            }
            int maxFrequency = 0, minLen = 0;
            for (Map.Entry<Integer, int[]> entry : map.entrySet()) {
                int[] arr = entry.getValue();
                if (arr[0] > maxFrequency) {
                    maxFrequency = arr[0];
                    minLen = arr[2] - arr[1] + 1;
                } else if (maxFrequency == arr[0]) {
                    if (arr[2] - arr[1] + 1 < minLen) minLen = arr[2] - arr[1] + 1;
                }
            }
            return minLen;
        }
        // 2
        public int findShortestSubArray(int[] nums) {
            HashMap<Integer, int[]> map = new HashMap<>();
            for (int i = 0; i < nums.length; i++) {
                if (map.containsKey(nums[i])) {
                    map.get(nums[i])[0]++;
                    map.get(nums[i])[2] = i;
                } else {
                    map.put(nums[i], new int[]{1, i, i});
                }
            }
            int maxFrequency = 0, minLen = 0;
            for (Map.Entry<Integer, int[]> entry : map.entrySet()) {
                int[] arr = entry.getValue();
                if (arr[0] > maxFrequency) {
                    maxFrequency = arr[0];
                    minLen = arr[2] - arr[1] + 1;
                } else if (arr[0] == maxFrequency) {
                    if (arr[2] - arr[1] + 1 < minLen) {
                        minLen = arr[2] - arr[1] + 1;
                    }
                }
            }
            return minLen;
        }
        // 3
        public int findShortestSubArray(int[] nums) {
            HashMap<Integer, int[]> map = new HashMap<>();
            for (int i = 0; i < nums.length; i++) {
                if (map.containsKey(nums[i])) {
                    int[] arr = map.get(nums[i]);
                    arr[0]++;
                    arr[2] = i;
                } else {
                    map.put(nums[i], new int[]{1, i, i});
                }
            }
            int maxFrequency = 0, minLength = 0;
            for (Map.Entry<Integer, int[]> entry : map.entrySet()) {
                int[] arr = entry.getValue();
                if (arr[0] > maxFrequency) {
                    maxFrequency = arr[0];
                    minLength = arr[2] - arr[1] + 1;
                } else if (arr[0] == maxFrequency) {
                    if (arr[2] - arr[1] + 1 < minLength) minLength = arr[2] - arr[1] + 1;
                }
            }
            return minLength;
        }
    }

    // 704 Binary Search
    class Solution {
        // 1
        public int search(int[] nums, int target) {
            int pivot, left = 0, right = nums.length - 1;
            while (left <= right) {
                pivot = left + (right - left) / 2;
                if (nums[pivot] == target) return pivot;
                if (nums[pivot] < target) {
                    left = pivot + 1;
                } else {
                    right = pivot - 1;
                }
            }
            return -1;
        }
        // 2
        public int search(int[] nums, int target) {
            int left = 0, right = nums.length - 1;
            while (left <= right) {
                int pivot = left + (right - left) / 2;
                if (nums[pivot] == target) return pivot;
                if (nums[pivot] < target) {
                    left = pivot + 1;
                } else {
                    right = pivot - 1;
                }
            }
            return -1;
        }
        // 3
        public int search(int[] nums, int target) {
            int left = 0, right = nums.length - 1;
            while (left <= right) {
                int pivot = left + (right - left) / 2;
                if (nums[pivot] == target) return pivot;
                if (nums[pivot] > target) {
                    right = pivot - 1;
                } else {
                    left = pivot + 1;
                }
            }
            return -1;
        }
    }

    // 724 数组的中心索引
    class Solution {
        // 1
        public int pivotIndex(int[] nums) {
            int total = Arrays.stream(nums).sum(), sumLeft = 0;
            for (int i = 0; i < nums.length; i++) {
                if (total - sumLeft - nums[i] == sumLeft) return i;
                sumLeft += nums[i];
            }
            return -1;
        }
        // 2
        public int pivotIndex(int[] nums) {
            int total = Arrays.stream(nums).sum(), leftSum = 0;
            for (int i = 0; i < nums.length; i++) {
                if (total - nums[i] - leftSum == leftSum) {
                    return i;
                } else {
                    leftSum += nums[i];
                }
            }
            return -1;
        }
        // 3
        public int pivotIndex(int[] nums) {
            int total = Arrays.stream(nums).sum(), leftSum = 0;
            for (int i = 0; i < nums.length; i++) {
                if (total - leftSum - nums[i] == leftSum) {
                    return i;
                }
                leftSum += nums[i];
            }
            return -1;
        }
        // 3
        public int pivotIndex(int[] nums) {
            int total = Arrays.stream(nums).sum(), leftSum = 0;
            for (int i = 0; i < nums.length; i++) {
                if (total - leftSum - nums[i] == leftSum) {
                    return i;
                }
                leftSum += nums[i];
            }
            return -1;
        }
    }

    // 728 自除数
    // 1
    class Solution {
        public List<Integer> selfDividingNumbers(int left, int right) {
            List<Integer> ans = new ArrayList<>();
            for (int n = left; n <= right; n++) {
                if (selfDividing(n)) ans.add(n);
            }
            return ans;
        }

        public boolean selfDividing (int n) {
            int x = n;
            while (x > 0) {
                int d = x % 10;
                if (d == 0 || (n % d) != 0) return false;
                x /= 10;
            }
            return true;
        }
    }
    // 2
    class Solution {
        public List<Integer> selfDividingNumbers(int left, int right) {
            List<Integer> ans = new ArrayList<>();
            for (int i = left; i <= right ; i++) {
                if (selfDividing(i)) {
                    ans.add(i);
                }
            }
            return ans;
        }

        public boolean selfDividing(int n) {
            int x = n;
            while (x > 0) {
                int a = x % 10;
                if (a == 0 || n % a != 0) {
                    return false;
                }
                x /= 10;
            }
            return true;
        }
    }
    // 3
    class Solution {
        public List<Integer> selfDividingNumbers(int left, int right) {
            List<Integer> ans = new ArrayList<>();
            for (int i = left; i <= right; i++) {
                if (selfDividing(i)) {
                    ans.add(i);
                }
            }
            return ans;
        }

        public boolean selfDividing(int n) {
            int x = n;
            while (x != 0) {
                int last = x % 10;
                x /= 10;
                if (last == 0 || n % last != 0) {
                    return false;
                }
            }
            return true;
        }
    }


    // 733 Flood Fill
    // 1
    class Solution {
        public int[][] floodFill (int[][] image, int sr, int sc, int newColor) {
            int color = image[sr][sc];
            if (color != newColor) {
                dfs(image, sr, sc, color, newColor);
            }
            return image;
        }

        public void dfs(int[][] image, int r, int c, int color, int newColor) {
            if (image[r][c] == color) {
                image[r][c] = newColor;
                if (r >= 1) {
                    dfs(image, r - 1, c, color, newColor);
                }
                if (c >= 1) {
                    dfs(image, r, c - 1, color, newColor);
                }
                if (r + 1 < image.length) {
                    dfs(image, r + 1, c, color, newColor);
                }
                if (c + 1 < image[0].length) {
                    dfs(image, r, c + 1, color, newColor);
                }
            }
        }
    }

    // 2
    class Solution {
        public int[][] floodFill (int[][] image, int sr, int sc, int newColor) {
            int color = image[sr][sc];
            if (color != newColor) {
                dfs(image, sr,sc,color,newColor);
            }
            return image;
        }

        public void dfs(int[][] image, int r, int c, int color, int newColor) {
            if (image[r][c] == color) {
                image[r][c] = newColor;
                if (r > 0) {
                    dfs(image, r - 1, c, color, newColor);
                }
                if (r < image.length - 1) {
                    dfs(image, r + 1, c, color, newColor);
                }
                if (c > 0) {
                    dfs(image, r, c - 1, color, newColor);
                }
                if (c < image[0].length - 1) {
                    dfs(image, r, c + 1, color, newColor);
                }
            }
        }
    }
    // 3
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int color = image[sr][sc];
        if (color != newColor) {
            dfs(image, sr, sc, color, newColor);
        }
        return image;
    }
    public void dfs(int[][] image, int r, int c, int color, int newColor) {
        if (color == image[r][c]) {
            image[r][c] = newColor;
            if (r > 0) {
                dfs(image, r - 1, c, color, newColor);
            }
            if (r < image.length - 1) {
                dfs(image, r + 1, c, color, newColor);
            }
            if (c > 0) {
                dfs(image, r, c - 1, color, newColor);
            }
            if (c < image[0].length - 1) {
                dfs(image, r, c + 1, color, newColor);
            }
        }
    }

    // 744 比目标字母大的最小字母
    class Solution {
        // 1
        public char nextGreatestLetter(char[] letters, char target) {
            for (char c : letters) {
                if (c > target) {
                    return c;
                }
            }
            return letters[0];
        }
        // 2
        public char nextGreatestLetter(char[] letters, char target) {
            for (char letter : letters) {
                if (letter > target) {
                    return letter;
                }
            }
            return letters[0];
        }
        // 3 略
    }

    // 746 Climb stairs minimum
    class Solution {
        // 1
        public int minCostClimbingStairs(int[] cost) {
            int prev = 0, curr = 0;
            for (int i = 2; i <= cost.length; i++) {
                int next = Math.min(curr + cost[i - 1], prev + cost[i - 2]);
                prev = curr;
                curr = next;
            }
            return curr;
        }
        // 2 3 略
    }

    // 766 ToeplizMatrix
    class Solution {
        // 1
        public boolean isToeplitzMatrix(int[][] matrix) {
            int r = matrix.length, c = matrix[0].length;
            for (int i = 1; i < r; i++){
                for (int j = 1; j < c; j++){
                    if (matrix[i][j] != matrix[i - 1][j - 1]) {
                        return false;
                    }
                }
            }
            return true;
        }
        // 2
        public boolean isToeplitzMatrix(int[][] matrix) {
            for (int r = 1; r < matrix.length; r++) {
                for (int c = 1; c < matrix[0].length; c++) {
                    if (matrix[r][c] != matrix[r - 1][c - 1]) {
                        return false;
                    }
                }
            }
            return true;
        }
    }

    // 796 rotating string
    // 1
    class Solution {
        // 1
        public boolean rotateString(String A, String B) {
            return A.length() == B.length() && (A + A).contains(B);
        }
        // 2
        public boolean rotateString(String A, String B) {
            if (A.length() != B.length()) {
                return false;
            }
            String doubleA = A + A;
            return doubleA.contains(B);
        }
    }

    // 804 Unique Morse Representations
    class Solution {
        // 1
        public int uniqueMorseRepresentations(String[] words) {
            String[] MORSE = new String[]{".-","-...","-.-.","-..",".","..-.","--.",
                    "....","..",".---","-.-",".-..","--","-.",
                    "---",".--.","--.-",".-.","...","-","..-",
                    "...-",".--","-..-","-.--","--.."};

            Set<String> seen = new HashSet<>();
            for (String word : words) {
                // StringBuffer已废
                StringBuilder code = new StringBuilder();
                for (char c : word.toCharArray()) {
                    String charCode = MORSE[c - 'a'];
                    code.append(charCode);
                }
                seen.add(code.toString());
            }
            return seen.size();
        }
    }
    // 2 3 略

    // 806 写字符串需要的行数
    class Solution {
        // 1
        public int[] numberOfLines(int[] widths, String S) {
            int lines = 1, width = 0;
            for (char c : S.toCharArray()) {
                int w = widths[c - 'a'];
                width += w;
                if (width > 100) {
                    lines++;
                    width = w;
                }
            }
            return new int[]{lines, width};
        }
        // 2
        public int[] numberOfLines(int[]widths, String S) {
            int lineLength = 0, lineCounts = 1;
            for (char c : S.toCharArray()) {
                int cLength = widths[c - 'a'];
                lineLength += cLength;
                if (lineLength > 100) {
                    lineCounts++;
                    lineLength = cLength;
                }
            }
            return new int[] {lineCounts, lineLength};
        }
        // 3 略
    }

    // 811 子域名访问计数
    class Solution {
        // 1
        public List<String> subdomainVisits(String[] cpdomains) {
            Map<String, Integer> counts = new HashMap();
            for (String domain: cpdomains) {
                String[] cpinfo = domain.split("\\s+");
                String[] frags = cpinfo[1].split("\\.");
                int count = Integer.valueOf(cpinfo[0]);
                // 当前域名字符串
                String cur = "";
                for (int i = frags.length - 1; i >= 0; --i) {
                    cur = frags[i] + (i < frags.length - 1 ? "." : "") + cur;
                    counts.put(cur, counts.getOrDefault(cur, 0) + count);
                }
            }

            List<String> ans = new ArrayList();
            for (String dom: counts.keySet())
                ans.add("" + counts.get(dom) + " " + dom);
            return ans;
        }
        // 2
        public List<String> subdomainVisits(String[] cpdomains) {
            Map<String, Integer> counts = new HashMap();
            for (String domain: cpdomains) {
                String[] cpinfo = domain.split("\\s+");
                String[] frags = cpinfo[1].split("\\.");
                int count = Integer.valueOf(cpinfo[0]);
                // 当前域名字符串
                String cur = "";
                for (int i = frags.length - 1; i >= 0; --i) {
                    if (i == frags.length - 1) {
                        cur = frags[i];
                    } else {
                        cur = frags[i] + "." + cur;
                    }
                    counts.put(cur, counts.getOrDefault(cur, 0) + count);
                }
            }

            List<String> ans = new ArrayList();
            for (String dom: counts.keySet())
                ans.add("" + counts.get(dom) + " " + dom);
            return ans;
        }
        // 3 略
    }

    // 819 Most Common Word
    class Solution {
        // 1
        public String mostCommonWord(String paragraph, String[] banned) {
            paragraph += ".";

            Set<String> banset = new HashSet<>();
            for (String word: banned) banset.add(word);

            Map<String, Integer> count = new HashMap<>();
            String ans = "";
            int ansfreq = 0;

            StringBuilder word = new StringBuilder();
            for (char c: paragraph.toCharArray()) {
                if (Character.isLetter(c)) {
                    word.append(Character.toLowerCase(c));
                } else if (word.length() > 0) {
                    String finalword = word.toString();
                    if (!banset.contains(finalword)) {
                        count.put(finalword, count.getOrDefault(finalword, 0) + 1);
                        if (count.get(finalword) > ansfreq) {
                            ans = finalword;
                            ansfreq = count.get(finalword);
                        }
                    }
                    word = new StringBuilder();
                }
            }
            return ans;
        }

        // 2 3 略
    }

    // 821 Shortest Distance to Character
    class Solution {
        // 1
        public int[] shortestToChar(String S, char C) {
            int[] ans = new int[S.length()];

            int prev = Integer.MIN_VALUE / 2;
            for (int i = 0; i < S.length(); ++i) {
                if (S.charAt(i) == C) prev = i;
                ans[i] = i - prev;
            }

            prev = Integer.MAX_VALUE / 2;
            for (int i = S.length()-1; i >= 0; --i) {
                if (S.charAt(i) == C) prev = i;
                ans[i] = Math.min(ans[i], prev - i);
            }

            return ans;
        }
        // 2 3 略
    }

    // 830 Position of Large Groups
    class Solution {
        // 1 2 3
        public List<List<Integer>> largeGroupPositions(String s) {
            List<List<Integer>> ret = new ArrayList<>();
            int n = s.length();
            int num = 1;
            for (int i = 0; i < n; i++) {
                if (i == n - 1 || s.charAt(i) != s.charAt(i + 1)) {
                    if (num >= 3) {
                        ret.add(Arrays.asList(i - num + 1, i));
                    }
                    num = 1;
                } else {
                    num++;
                }
            }
            return ret;
        }
    }

    // 832 Flip Image
    // 1
    class Solution {
        public int[][] flipAndInvertImage(int[][] A) {
            int C = A[0].length;
            for (int[] row: A)
                for (int i = 0; i < (C + 1) / 2; ++i) {
                    int tmp = row[i] ^ 1;
                    row[i] = row[C - 1 - i] ^ 1;
                    row[C - 1 - i] = tmp;
                }
            return A;
        }
    }
    // 2 3 略

    // 836 Rectangle Overlap
    class Solution {
        // 1 2 3
        public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
            return (Math.min(rec1[2], rec2[2]) > Math.max(rec1[0], rec2[0]) &&
                    Math.min(rec1[3], rec2[3]) > Math.max(rec1[1], rec2[1]));
        }
    }

    // 844 含退格的字符串
    // 1 2 3
    class Solution {
        public boolean backspaceCompare(String S, String T) {
            return build(S).equals(build(T));
        }

        public String build(String S) {
            Deque<Character> ans = new ArrayDeque<>();
            for (char c: S.toCharArray()) {
                if (c != '#')
                    ans.push(c);
                else if (!ans.isEmpty())
                    ans.pop();
            }
            return String.valueOf(ans);
        }
    }
}

// 853 Mountain Peek
// 1 2 3
class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int left = 0, right = arr.length - 1, ans = 0;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] > arr[mid + 1]) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}

// 859 Buddy Strings
class Solution {
    // 1 2 3
    public boolean buddyStrings(String A, String B) {
        if (A.length() != B.length()) return false;
        if (A.equals(B)) {
            int[] count = new int[26];
            for (int i = 0; i < A.length(); ++i)
                count[A.charAt(i) - 'a']++;

            for (int c: count)
                if (c > 1) return true;
            return false;
        } else {
            int first = -1, second = -1;
            for (int i = 0; i < A.length(); ++i) {
                if (A.charAt(i) != B.charAt(i)) {
                    if (first == -1)
                        first = i;
                    else if (second == -1)
                        second = i;
                    else
                        return false;
                }
            }

            return second != -1 && A.charAt(first) == B.charAt(second) && A.charAt(second) == B.charAt(first);
        }
    }
}

// 860 Lemonade Change
class Solution {
    // 1 2
    public boolean lemonadeChange(int[] bills) {
        int five = 0, ten = 0;
        for (int bill : bills) {
            if (bill == 5) {
                five++;
            } else if (bill == 10) {
                if (five == 0) {
                    return false;
                }
                five--;
                ten++;
            } else {
                if (five > 0 && ten > 0) {
                    five--;
                    ten--;
                } else if (five >= 3) {
                    five -= 3;
                } else {
                    return false;
                }
            }
        }
        return true;
    }

    // 3
    public boolean lemonadeChange(int[] bills) {
        int five = 0, ten = 0;
        for (int bill : bills) {
            if (bill == 5) {
                five++;
            } else if (bill == 10) {
                if (five > 0) {
                    five--;
                    ten++;
                } else {
                    return false;
                }
            } else {
                if (five > 0 && ten > 0) {
                    five--;
                    ten--;
                } else if (five >= 3) {
                    five -= 3;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
}


// 867 Transpose Matrix
class Solution {
    // 1 2 3
    public int[][] transpose(int[][] matrix) {
        int[][] transposed = new int[matrix[0].length][matrix.length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                transposed[j][i] = matrix[i][j];
            }
        }
        return transposed;
    }
}

// 872. Leaf-Similar Trees
// 1 2 3
class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> seq1 = new ArrayList<Integer>();
        if (root1 != null) {
            dfs(root1, seq1);
        }

        List<Integer> seq2 = new ArrayList<Integer>();
        if (root2 != null) {
            dfs(root2, seq2);
        }

        return seq1.equals(seq2);
    }

    public void dfs(TreeNode node, List<Integer> seq) {
        if (node.left == null && node.right == null) {
            seq.add(node.val);
        } else {
            if (node.left != null) {
                dfs(node.left, seq);
            }
            if (node.right != null) {
                dfs(node.right, seq);
            }
        }
    }
}

// 876. Middle of the Linked List
class Solution {
    // 1 2 3
    public ListNode middleNode(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

// 884. Uncommon Words from Two Sentences
class Solution {
    // 1 2 3
    public String[] uncommonFromSentences(String A, String B) {
        Map<String, Integer> count = new HashMap<>();
        for (String word: A.split(" "))
            count.put(word, count.getOrDefault(word, 0) + 1);
        for (String word: B.split(" "))
            count.put(word, count.getOrDefault(word, 0) + 1);

        List<String> ans = new LinkedList<>();
        for (String word: count.keySet())
            if (count.get(word) == 1)
                ans.add(word);

        return ans.toArray(new String[ans.size()]);
    }
}
